package com.ljy.my_study.lintcode.Delete_Node_in_a_Linked_List;

/**
 * @author James
 * @date 2018年9月28日
 */
public class TestMain {
	public static void main(String[] args) {
//		removeNthFromEnd();
//		int[] nums= {1};
		int[] nums= {1,2,3,4,5,6};
		ListNode head=createNode(nums);
		System.out.println(head);
		head=removeNthFromEnd(head,1);
		System.out.println(head);
	}
	
	private static ListNode createNode(int[] nums) {
		ListNode head=null;
		ListNode node=null;
		for(int i=0;i<=nums.length-1;i++) {
			if(i==0) {
				node=head=new ListNode(nums[0]);
			}
			if(i!=nums.length-1) {
				node.next=new ListNode(nums[i+1]);
				node=node.next;
			}
		}
		return head;
	}
	
	// 给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。
	//
	// 样例
	// Linked list is 1->2->3->4, and given node 3, delete the node in place 1->2->4
	public void deleteNode(ListNode node) {
		node.val = node.next.val;
		node.next = node.next.next;
	}
//	删除链表中倒数第n个节点
//	给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。
//
//
//
//	样例
//	给出链表1->2->3->4->5->null和 n = 2.
//
//	删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.
//
//	挑战
//	O(n)时间复杂度
//
//	注意事项
//	链表中的节点个数大于等于n
	public static ListNode removeNthFromEnd(ListNode head, int n) {
        int len=0;
        ListNode node=head;
        while(node!=null){
            len++;
            node=node.next;
        }
        int count=0;
        node=head;
        ListNode lastNode=null;
        while(count<len-n){
        	lastNode=node;
            node=node.next;
            count++;
        }
        if(node.next!=null) {
        	node.val=node.next.val;
        	node.next=node.next.next;
        }else {
        	if(lastNode!=null)lastNode.next=null;
        	if(head==node)head=node=null;
        	else node=null;
        }
        return head;
    }

	public static class ListNode {
		int val;
		ListNode next;

		ListNode(int val) {
			this.val = val;
			this.next = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\",\"next\":\"" + next + "\"} ";
		}
		
	}
}
